package com.arron.algorithm.leetcodetop100.回溯.排列and组合and子集;

import java.util.ArrayList;
import java.util.List;

public class 组合 {

    List<List<Integer>> allSubList;
    public List<List<Integer>> combine(int n, int k) {

        List<Integer> subList = new ArrayList<>();
        allSubList = new ArrayList<>();
        subsets(n,subList,1,k);
        return allSubList;
    }

    public void subsets(int n,List<Integer> subList,int start,int k){

        if (subList.size() == k){
            allSubList.add(new ArrayList<>(subList));
            return;
        }


        for (int i = start; i <=n; i++) {
            subList.add(i);
            subsets(n,subList,i+1,k);
            subList.remove(subList.size()-1);
        }

    }

    /**
     * 优化 搜索的上界
     * @param n
     * @param subList
     * @param start
     * @param k
     */
    public void subsetPlus(int n,List<Integer> subList,int start,int k){

        if (subList.size() == k){
            allSubList.add(new ArrayList<>(subList));
            return;
        }


        for (int i = start; i <= n-(k-subList.size())+1; i++) {
            subList.add(i);
            subsets(n,subList,i+1,k);
            subList.remove(subList.size()-1);
        }

    }

    public static void main(String[] args) {
        组合 combine = new 组合();
        System.out.println(combine.combine(20, 10));
    }
}
